package _04_queue.my_implements;

import _04_queue.AbstractQueue;

import java.util.Iterator;

/**
 * @author: mornd
 * @dateTime: 2023/6/5 - 14:42
 * 环形数组实现（推荐使用）
 * （与实现2类似，head，tail 不存储下标（会一直自增）而是根据head，tail求出头尾位置， head，tail自增超过数组长度是正常的
 * 不用特意维护head，tail的值，而是根据head，tail的值求出队列头尾位置
 */
public class ArrayQueue<E> extends AbstractQueue<E> {
    Object[] data;

    // 头指针
    private int head = 0;
    // 尾指针
    private int tail = 0;

    public ArrayQueue(int capacity) {
        if (capacity < 0) {
            throw new IllegalArgumentException();
        }
        // 判断 capacity 是否为2^n
//        if((capacity & capacity -1) != 0) {
//            // 不是2^n
//        }

        capacity = 1 << ((int) (Math.log10(capacity - 1) / Math.log10(2)) + 1);

        data = new Object[capacity];
    }

    /**
     * 给定一个数c，求离c最进，比c大的2^n数
     *
     * @param args
     */
    public static void main(String[] args) {
        int c = 31;
        /*
            方式1
            已知：
            2的4次方 = 16
            2的5次方 = 32
            2的6次方 = 64

            求出以2为底 30的对数 + 1
            log2(30) + 1

            java没有直接求以2为底的对数，需转换为
            log2(x) = log10(x) / log10(2)
         */

        //Math.log(); // 以自然数为底的对数
        //Math.log10(); // 以10为底的对数

//        double v = Math.log10(c) / Math.log10(2) + 1; // // 5.906890595608519
        int v = (int) (Math.log10(c) / Math.log10(2)) + 1; // 5
        /*
            上面求出v的值为5，如何快速得到2^5
            1<<1 = 2
            1<<2 = 4
            1<<3 = 8
            1<<4 = 16
            1<<5 = 32
            得到的公式：1 << 5
         */
        System.out.println(1 << 5);
        System.out.println(Math.pow(2, 5)); // 得到2的5次方

        /*
            如果c本身就是2的n次方，需将c-1
         */
        int v2 = 1 << (int) (Math.log10(c - 1) / Math.log10(2)) + 1;
        System.out.println(v2);

        /*
            方式2，位运算
         */
        int a = 40;
        a -= 1;
        a |= a >> 1;
        a |= a >> 2;
        a |= a >> 4;
        a |= a >> 8;
        a |= a >> 16;
        a += 1;
        System.out.println(a);
    }

    @Override
    public boolean offer(E e) {
        if (isFull()) {
            return false;
        }

//        data[tail % data.length] = e; // 第1版
//        Integer.toUnsignedLong 可以解决Integer存储溢出问题，将值转换为long类型
//        data[(int) (Integer.toUnsignedLong(head) % data.length)] = e; // 第2版

        /*
            必须先保证数组长度是2^n，才能替换成下面的位运算符
            该运算得到的是 tail % data.length 的值，可解决tail超出int最大存储范围问题
         */
        data[tail & (data.length - 1)] = e; // 第3版
        tail++;
        return true;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        int i = head & data.length - 1;
        Object e = data[i];
        data[i] = null;
        head++;
        return (E) e;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
//        return (E) data[(int) (Integer.toUnsignedLong(head) % data.length)];
        return (E) data[head & data.length - 1];
    }

    @Override
    public boolean isEmpty() {
        return head == tail;
    }

    @Override
    public boolean isFull() {
        return tail - head == data.length;
    }

    @Override
    public Iterator<E> iterator() {
        return new Itr();
    }

    private class Itr implements Iterator<E> {
        int cursor = head;

        @Override
        public boolean hasNext() {
            return cursor != ArrayQueue.this.tail;
        }

        @Override
        public E next() {
//            Object e = data[cursor % data.length];
            Object e = data[cursor & ArrayQueue.this.data.length - 1];
            cursor++;
            return (E) e;
        }
    }
}
